// dfs
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        if (!root->left && !root->right) return 1;
        if (!root->left) return minDepth(root->right) + 1; // 注意，如果不判断，只有一个子树的会被当成最浅的
        if (!root->right) return minDepth(root->left) + 1;
        return min(minDepth(root->left), minDepth(root->right)) + 1;
    }
};

// 个
class Solution {
public:
    int minHeight = INT_MAX;
    void helper(TreeNode* root, int tmp) {
        if (!root) return;
        if (!root->left && !root->right) {
            minHeight = min(minHeight, tmp);
        }
        helper(root->left, tmp + 1);
        helper(root->right, tmp + 1);
    }
    int minDepth(TreeNode* root) {
        helper(root, 1);
        return minHeight == INT_MAX ? 0: minHeight;
    }
};

// bfs
// bfs的性质保证了最先搜索到的叶子节点的深度一定最小，当找到一个叶子节点时，直接返回它的深度。
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        queue<pair<TreeNode*, int>> q;
        q.emplace(root, 1);
        while (!q.empty()) {
            TreeNode* tmp;
            int val;
            tie(tmp, val) = q.front();
            q.pop();
            if (!tmp->left && !tmp->right)
                // minHeight = min(minHeight, val);
                return val;
            if (tmp->left) q.emplace(tmp->left, val + 1);
            if (tmp->right) q.emplace(tmp->right, val + 1);
        }
        return 0;
    }
};

// bfs之层序遍历的思路
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        queue<TreeNode*> q;
        q.emplace(root);
        int height = 0;
        while (!q.empty()) {
            int len = q.size();
            height++;
            for (int i = 0; i < len; ++i) {
                TreeNode* tmp = q.front();
                q.pop();
                if (!tmp->left && !tmp->right)
                    return height;
                if (tmp->left) q.emplace(tmp->left);
                if (tmp->right) q.emplace(tmp->right);
            }
        }
        return height;
    }
};
